package list;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * An abstract class that has most of the methods of java.util.List implemented;
 * the user only needs to implement a few methods for all other methods to
 * work. Most methods are implemented in the most straight forward ways using
 * the methods subclasses must implement. This can be inefficient depending on 
 * the application. Subclasses should re-implement methods whenever there is a 
 * more efficient alternative. The implementation details are in the
 * documentations of each method.
 * 
 * @author Shimu
 * @date 19-Aug-2012
 */
public abstract class IndexableList<T> implements List<T> {

    /** The total number of elements in this List */
    protected int size;

    /**
     * The index considered index 0.
     */
    private final int INDEX_OFFSET;

    protected IndexableList(int size) {
        this(0, size);
    }

    private IndexableList(int indexOffset, int size) {
        this.size = size;
        this.INDEX_OFFSET = indexOffset;
    }

    public int size() {
        return size;
    }

    /**
     * Returns true if size == 0.
     * 
     * @return 
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns true if indexOf(o) != -1.
     * 
     * @param o
     * @return 
     */
    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    /**
     * The iterator returned by this method uses IndexableList.get(int) in 
     * Iterator.next(), and uses IndexableList.remove(int) in Iterator.remove().
     * 
     * @return 
     */
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            private int currentIndex = 0;

            public boolean hasNext() {
                return currentIndex < size();
            }

            public T next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                T returnVal = get(currentIndex);
                currentIndex++;
                calledRemove = true;
                return returnVal;
            }

            /** True if remove has already been called after the last call
            to next */
            private boolean calledRemove = false;

            @Override
            public void remove() {
                if (calledRemove) {
                    throw new IllegalStateException("Remove has already been "
                            + "called after the last call to next!");
                } else if (currentIndex == 0) {
                    throw new IllegalStateException("The next method has not "
                            + "yet been called!");
                } 
                currentIndex--;
                calledRemove = true;
                IndexableList.this.remove(currentIndex);
            }
        };
    }

    /**
     * Creates a new array with the same size as this IndexableList and insert each
     * element of this IndexableList into the array.
     * 
     * @return 
     */
    @Override
    public T[] toArray() {
        T[] array = (T[]) new Object[size()];
        for (int i = 0; i < size(); i++) {
            array[i] = get(i);
        }
        return array;
    }

    @Override
    public Object[] toArray(Object[] a) {
        if (a.length >= size()) {
            // Put the elements into the given array if it is large enough
            for (int i = 0; i < size(); i++) {
                a[i] = get(i);
            }
            // Initialize the rest of the given array to null
            for (int i = size(); i < a.length; i++) {
                a[i] = null;
            }
            return a;
        } else {
            // Otherwise allocated a new array
            return toArray();
        }
    }

    @Override
    public boolean containsAll(Collection c) {
        for (Object o : c) {
            if (!this.contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public int indexOf(Object o) {
        for (int i = 0; i < this.size(); i++) {
            if (get(i).equals(o)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        for (int i = size() - 1; i >= 0; i--) {
            if (get(i).equals(o)) {
                return i;
            }
        }
        return -1;
    }

    private class MyListIterator implements ListIterator<T> {

        /** Neither next() nor previous() was called */
        private static final int NO_CALL = 0;

        /** The last call was to next() */
        private static final int CALLED_NEXT = 1;

        /** The last call was to previous() */
        private static final int CALLED_PREVIOUS = 2;

        /** The current state of the iterator */
        private int state;

        /** 
         * True if add or remove have been called after the last call to next 
         * or previous. False otherwise. Calls to set is ignored.
         */
        private boolean addedRemovedElement;

        /** 
         * The cursor position, the next element the same as the cursor
         * position, the previous element is one less than the cursor position.
         * The last element returned by next is one less than the 
         * cursor position. The last element returned by previous is the same
         * as the cursor position.
         * 
         *          Element[0] Element[1] Element[2] ... Element[n]   
         *         ^          ^          ^          ^              ^
         * Cursor: 0          1          2          3              n+1
         * 
         * Summary:
         * next element = last element returned by previous = cursor
         * previous element = last element returned by next = cursor - 1 
         */
        private int cursor;

        public MyListIterator() {
            this(0);
        }

        public MyListIterator(int cursor) {
            this.state = NO_CALL;
            this.addedRemovedElement = false;
            this.cursor = cursor;
        }

        public boolean hasNext() {
            return cursor < size();
        }

        public boolean hasPrevious() {
            return cursor > 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            T returnVal = get(nextIndex());
            cursor++;
            state = CALLED_NEXT;
            addedRemovedElement = false;
            return returnVal;
        }

        public T previous() {
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }

            T returnVal = get(previousIndex());
            cursor--;
            state = CALLED_PREVIOUS;
            addedRemovedElement = false;
            return returnVal;
        }

        public void set(T e) {
            if (addedRemovedElement) {
                throw new IllegalStateException("One of add or remove has been"
                        + " called after the last call to previous or next!");
            }

            if (state == CALLED_NEXT) {
                IndexableList.this.set(cursor - 1, e);
            } else if (state == CALLED_PREVIOUS) {
                IndexableList.this.set(cursor, e);
            } else {
                throw new IllegalStateException("Neither next nor previous "
                        + "was called!");
            }
        }

        public void add(T e) {
            IndexableList.this.add(cursor, e);
            cursor++;
            addedRemovedElement = true;
        }

        public void remove() {
            if (addedRemovedElement) {
                throw new IllegalStateException("One of add or remove has been"
                        + " called after the last call to previous or next!");
            }
            if (state == CALLED_NEXT) {
                IndexableList.this.remove(cursor - 1);
            } else if (state == CALLED_PREVIOUS) {
                IndexableList.this.remove(cursor);
            } else {
                throw new IllegalStateException("Neither next nor previous "
                        + "was called!");
            }
            addedRemovedElement = true;
        }
    }

    @Override
    public ListIterator<T> listIterator() {
        return new MyListIterator(0);
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        return new MyListIterator(index);
    }

    @Override
    public boolean add(T e) {
        add(size, e);
        return true;
    }

    /*
    @Override
    public List<T> subList(int fromIndex, int toIndex) {
    return new IndexableList<T>(fromIndex, toIndex - fromIndex);
    }*/
    @Override
    public boolean addAll(Collection c) {
        return this.addAll(size, c);
    }

    /**
     * Calls add(T) on each element of the given Collection c. This is a 
     * simple implementation which works but may be inefficient for some
     * applications. 
     * 
     * @param index
     * @param c
     * @return 
     */
    @Override
    public boolean addAll(int index, Collection c) {
        int i = index;
        int originalSize = this.size();
        for (Object o : c) {
            this.add(i, (T) o);
            i++;
        }
        return originalSize != this.size();
    }

    @Override
    public boolean remove(Object o) {
        int i = this.indexOf(o);
        if (i != -1) {
            this.remove(i);
            return true;
        } else {
            return false;
        }
    }

    /**
     * Call remove(Object) on each element of the given Collection c.
     * Runtime is O(mn) where m is the runtime of remove(Object), and n
     * is the size of Collection c. Likely quadratic if remove uses linear
     * search to find the element to be removed.
     * 
     * @param c
     * @return 
     */
    @Override
    public boolean removeAll(Collection c) {
        int originalSize = this.size();
        for (Object element : c) {
            // removedElements will be false until this.remove returns true
            // afterwards it will stay true
            this.remove(element);
        }
        return originalSize != this.size();
    }

    @Override
    public boolean retainAll(Collection c) {
        int i = 0;
        int originalSize = this.size();
        while (i < this.size()) {
            if (c.contains(this.get(i))) {
                this.remove(i);
            } else {
                i++;
            }
        }
        return originalSize != this.size();
    }

    // ============= These Methods Need to be Implemented =============
    public abstract T get(int index);

    public abstract T set(int index, T element);

    public abstract List<T> subList(int fromIndex, int toIndex);

    @Override
    public abstract void add(int index, T element);

    @Override
    public abstract T remove(int index);

    @Override
    public abstract void clear();
}
